#include <iostream>
#include <fstream>
#include <sstream>
#include <cstdlib>
#include <string>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <list>
#include <cassert>
#include <utility>

// pour la seconde partie du projet
#include "expression_rationnelle.hpp"
#include "parser.hpp"

using namespace std;

////////////////////////////////////////////////////////////////////////////////

const unsigned int ASCII_A = 97;
const unsigned int ASCII_Z = ASCII_A + 26;
const bool DEBUG = false;

typedef size_t etat_t;
typedef unsigned char symb_t;
typedef set<etat_t> etatset_t;
typedef vector<vector<etatset_t> > trans_t;
typedef vector<etatset_t> epsilon_t;
typedef map<etatset_t, etat_t> map_t;

////////////////////////////////////////////////////////////////////////////////

struct sAutoNDE {
	// caractéristiques
	size_t nb_etats;
	size_t nb_symbs;
	size_t nb_finaux;

	etat_t initial;
	// état initial

	etatset_t finaux;
	// états finaux : finaux_t peut être un int*, un tableau dynamique comme vector<int>
	// ou une autre structure de donnée de votre choix.

	trans_t trans;
	// matrice de transition : trans_t peut être un int***, une structure dynamique 3D comme vector< vector< set<int> > >
	// ou une autre structure de donnée de votre choix.

	epsilon_t epsilon;
	// transitions spontanées : epsilon_t peut être un int**, une structure dynamique 2D comme vector< set<int> >
	// ou une autre structure de donnée de votre choix.
};

sAutoNDE constructionAutomate(sExpressionRationnelle er, int nb_symbs);
void compteSymboleExpr(sExpressionRationnelle er, int& cpt);

////////////////////////////////////////////////////////////////////////////////

bool FromFile(sAutoNDE& at, string path) {
	ifstream myfile(path.c_str(), ios::in);
	//un flux d'entree obtenu à partir du nom du fichier
	string line;
	// un ligne lue dans le fichier avec getline(myfile,line);
	istringstream iss;
	// flux associé à la chaine, pour lire morceau par morceau avec >> (comme cin)
	etat_t s(0), t(0);
	// deux états temporaires
	symb_t a(0);
	// un symbole temporaire

	if (myfile.is_open()) {
		// la première ligne donne 'nb_etats nb_symbs nb_finaux'
		do {
			getline(myfile, line);
		} while (line.empty() || line[0] == '#');
		// on autorise les lignes de commentaires : celles qui commencent par '#'
		iss.str(line);
		if ((iss >> at.nb_etats).fail() || (iss >> at.nb_symbs).fail()
				|| (iss >> at.nb_finaux).fail())
			return false;
		// la deuxième ligne donne l'état initial
		do {
			getline(myfile, line);
		} while (line.empty() || line[0] == '#');
		iss.clear();
		iss.str(line);
		if ((iss >> at.initial).fail())
			return -1;

		// les autres lignes donnent les états finaux
		for (size_t i = 0; i < at.nb_finaux; i++) {
			do {
				getline(myfile, line);
			} while (line.empty() || line[0] == '#');
			iss.clear();
			iss.str(line);
			if ((iss >> s).fail())
				continue;
			//        cerr << "s= " << s << endl;
			at.finaux.insert(s);
		}

		// on alloue les vectors à la taille connue à l'avance pour éviter les resize dynamiques
		at.epsilon.resize(at.nb_etats);
		at.trans.resize(at.nb_etats);
		for (size_t i = 0; i < at.nb_etats; ++i)
			at.trans[i].resize(at.nb_symbs);

		// lecture de la relation de transition
		while (myfile.good()) {
			line.clear();
			getline(myfile, line);
			if (line.empty() && line[0] == '#')
				continue;
			iss.clear();
			iss.str(line);

			// si une des trois lectures echoue, on passe à la suite
			if ((iss >> s).fail() || (iss >> a).fail() || (iss >> t).fail()
					|| (a < ASCII_A) || (a > ASCII_Z))
				continue;

			//test espilon ou non
			if ((a - ASCII_A) >= at.nb_symbs) {
				at.epsilon[s].insert(t);
			} else {
				at.trans[s][a - ASCII_A].insert(t);
				//TODO remplir trans
			}
		}
		myfile.close();
		return true;
	}
	return false;
	// on ne peut pas ouvrir le fichier
}

// -----------------------------------------------------------------------------
// Fonctions à compléter pour la première partie du projet
// -----------------------------------------------------------------------------

////////////////////////////////////////////////////////////////////////////////

bool ContientFinal(const sAutoNDE& at, const etatset_t& e)  //e = etat finaux
{

	//On parcours tous les états de l'ensemble d'états passé en paramètre.
	for (etatset_t::iterator it = e.begin(); it != e.end(); it++) 
	{
		//On parcours l'ensemble des états finaux de l'automate at
		for (etatset_t::iterator it2 = at.finaux.begin(); it2 != at.finaux.end(); it2++) 
		{
			if (*it == *it2) //Si automate contient un etat de e = contient un etat final
			{
				return true;
			}
		}
	}

	return false;
}

////////////////////////////////////////////////////////////////////////////////

bool EstDeterministe(const sAutoNDE& at) 
{

	//Parcours le tableau pour vérifier s'il y a des epsilon transitions
	for (unsigned int i = 0; i < at.epsilon.size(); i++) 
	{
		//S'il n'yen a pas, on retourne false
		if (at.epsilon[i].size() != 0) {
			return false;
		}
	}

	//Parcours des transitions de l'automate at
	for (unsigned int i = 0; i < at.trans.size(); i++) 
	{
		for (unsigned int j = 0; j < at.trans[i].size(); j++) 
		{
			//S'il y a plus d'une transitions qui part d'un état, c'est qu'il n'est pas déterministe
			if (at.trans[i][j].size() != 1) //i = etat, j = lettre
			{
				return false;
			}
		}
	}

	return true;
}

////////////////////////////////////////////////////////////////////////////////

void Fermeture(const sAutoNDE& at, etatset_t& e) 
{
	// Cette fonction clot l'ensemble d'états E={e_0, e_1, ... ,e_n} passé en
	// paramètre avec les epsilon transitions
	
	//On vérifie qu'il y a bien des epsilon transitions
	if (at.epsilon.size() > 0) 
	{
		//Parcours e
		for (etatset_t::iterator i = e.begin(); i != e.end(); i++) 
		{
			//Parcours les epsilon transitions de e
			for (etatset_t::iterator j = at.epsilon[*i].begin(); j != at.epsilon[*i].end(); j++) 
			{
				e.insert((*j));
			}
		}
	}
}

////////////////////////////////////////////////////////////////////////////////

etatset_t Delta(const sAutoNDE& at, const etatset_t& e, symb_t c) 
{
	etatset_t resultat = e;

	//On fait la fermeture sur e/resultat
	Fermeture(at, resultat);

	//Supprime les états qu'on avait dans e car on ne peut pas aller de l'état 1 à l'état 1 sans une lettre,
	for (etatset_t::iterator i = e.begin(); i != e.end(); i++)
	{
		resultat.erase(*i);
	}

	//Parcours e
	for (etatset_t::iterator i = e.begin(); i != e.end(); i++) 
	{
		//Parcours les états de e avec la lettre c
		for (etatset_t::iterator j = at.trans[(*i)][c - ASCII_A].begin(); j != at.trans[(*i)][c - ASCII_A].end(); j++) 
		{
			resultat.insert((*j));
		}
	}

	Fermeture(at, resultat);

	return resultat;
}

////////////////////////////////////////////////////////////////////////////////

bool Accept(const sAutoNDE& at, string str) {

	etatset_t ensembleEtat;

	ensembleEtat.insert(at.initial);

	//Si str = e = test du mot vide
	if(str[0] == 'e' && str.size() == 1) 
	{
		if(ContientFinal(at, ensembleEtat))
		{
			return true;
		}
		return false;
	}

	//Pour chaque caractère du mot testé
	for (unsigned int i = 0; i < str.size(); i++) 
	{
		//Si le mot a une lettre qui ne fait pas partie de l'alphabet de at, il n'est pas accepté.
		if((symb_t)(str[i] - ASCII_A) > at.nb_symbs)
		{
			return false;
		}
		
		//On insère dans ensembleEtat, tous les états parcouru par le mot.
		ensembleEtat = Delta(at, ensembleEtat, str[i]);

		if (ensembleEtat.size() == 0) 
		{
			return false;
		}
	}

	//On vérifie que dans ensembleEtat, il y a au moins un état final
	if (ContientFinal(at, ensembleEtat)) 
	{
		return true;
	}

	return false;
}

////////////////////////////////////////////////////////////////////////////////

//Fonction qui permet d'afficher des etatset_t
ostream& operator<<(ostream& out, const etatset_t& etats) 
{
	for (etatset_t::iterator it2 = etats.begin(); it2 != etats.end(); it2++) 
	{
		out << (*it2) << " ";
	}

	return out;
}

ostream& operator<<(ostream& out, const sAutoNDE& at) 
{
	bool contientEpsilon = false;

	out << "Nombre d'etats : " << at.nb_etats << std::endl;
	out << "Nombre d'etats finaux : " << at.nb_finaux << std::endl;
	out << "Nombre de symboles : " << at.nb_symbs << std::endl;

	//Parcours le tableau pour vérifier s'il y a des epsilon transitions
	for (unsigned int i = 0; i < at.epsilon.size(); i++) 
	{
		if (at.epsilon[i].size() != 0) {
			out << "Transitions spontannees : OUI" << std::endl;
			contientEpsilon = true;

			break;
		}
	}

	//Si pas de transitions spontannées
	if (contientEpsilon == false) 
	{
		out << "Transitions spontannees : NON" << std::endl;
	}

	out << "Etat Initial : " << at.initial << std::endl;

	out << "Etat Finaux : ";

	//On parcours tous les états finaux de at afin de les afficher
	for (set<etat_t>::iterator it = at.finaux.begin(); it != at.finaux.end(); it++) 
	{
		out << *it << ",";
	}

	out << std::endl << "\nTransitions : \n";

	etatset_t etatPourDelta;

	for (unsigned int i = 0; i < at.trans.size(); i++) 
	{
		for (unsigned int j = 0; j < at.nb_symbs; j++) 
		{
			//On insère l'état
			etatPourDelta.insert(i); 

			//Delta sur l'état
			etatPourDelta = Delta(at, etatPourDelta, ASCII_A + j); 

			//On affiche les transitions entre les états.
			out << "Delta(" << i << "," << (symb_t) (j + ASCII_A) << ") = {" << etatPourDelta << "}" << std::endl;

			//On supprime le contenu de etatPourDelta pour recommencer avec un autre état ou une autre lettre
			etatPourDelta.clear(); 
		}
	}
	
	//On affiche les e-transitions entre les états concernés.
	for(unsigned int i = 0; i < at.epsilon.size(); i++)
	{
		out << "Delta(" << i << ", e) = {" << at.epsilon[i] << "}" << std::endl;

	}

	return out;

}

////////////////////////////////////////////////////////////////////////////////

//Compare 2 etatset_t
bool compareEtatSet(etatset_t e1, etatset_t e2) 
{
	//Compare le premier etatset avec le deuxième
	for (etatset_t::const_iterator it = e2.begin(); it != e2.end(); it++) 
	{
		if (e1.count(*it) == 0) {
			return false;
		}
	}

	//Compare le deuxième avec le premier (dans le cas où e1.size < e2.size ou e1 = e2)
	for (etatset_t::const_iterator it = e1.begin(); it != e1.end(); it++) 
	{
		if (e2.count(*it) == 0) {
			return false;
		}
	}

	return true;
}

//Fonction qui permet d'enregistrer un automate dans un fichier texte, avec le même format que celui des exemples.
ofstream& operator<< (ofstream& file, const sAutoNDE at)
{
	file << at.nb_etats << " " << at.nb_symbs << " " << at.nb_finaux << "\n";
	file << at.initial << "\n";
	for (etatset_t::const_iterator it = at.finaux.begin(); it != at.finaux.end(); it++) //Etat finaux
	{
		file  << *it << "\n";
	}
	for (unsigned int i = 0; i < at.trans.size(); i++) //Parcours e
	{
		for(unsigned int k = 0; k < at.nb_symbs; k++)
		{
			for (etatset_t::iterator j = at.trans[(i)][k].begin(); j != at.trans[(i)][k].end(); j++) //Parcours les états de e avec la lettre c
			{
				file << i << " " << (symb_t)(k + ASCII_A) << " " << *j << "\n";
			}
		}
	}
	for(unsigned int i = 0; i < at.epsilon.size(); i++)
	{
		for(etatset_t::iterator j = at.epsilon[i].begin(); j != at.epsilon[i].end(); j++)
		{
			file << i << " e " << *j << "\n";
		}
	}

	return file;
}

sAutoNDE Determinize(const sAutoNDE& at) 
{

	sAutoNDE retour;

	//Si l'automate n'est pas déterministe.
	if (!EstDeterministe(at)) 
	{
		int k = 0;
		int tailleTableau = 0;

		//Stockage de tout les deltas
		etatset_t stockageDelta[100]; 
		etatset_t retourDelta;
		etatset_t etatPourDelta;

		//Correspondance des ensembles d'états avec un état
		map_t correspondanceEtat; 

		bool insert = true;
		bool continu = true;

		//On part de l'état initial
		etatPourDelta.insert(at.initial); 

		Fermeture(at, etatPourDelta);

		stockageDelta[tailleTableau] = etatPourDelta;
		tailleTableau++;

		//On l'ajoute dans la correspondance des états
		correspondanceEtat.insert(std::pair<etatset_t, etat_t>(etatPourDelta, 0)); 

		while (continu == true) 
		{
		
			//Parcours de chaque lettre
			for (unsigned int i = 0; i < at.nb_symbs; i++) 
			{
				insert = true;

				//Fermeture + delta sur l'état dans retourDelta, 1er tour de while = etat initial
				retourDelta = Delta(at, etatPourDelta, ASCII_A + i); 

				//Vérification s'il existe pas dans le tableau stockageDelta
				for (int j = 0; j < tailleTableau; j++) 
				{
					//Si l'état retourDelta existe alors insert = false
					if (compareEtatSet(stockageDelta[j], retourDelta)) 
					{
						insert = false;
						break;
					}
				}

				//S'il existe pas, insert = true et on insère dans le tableau stockageDelta et dans la map
				if (insert == true) 
				{
					stockageDelta[tailleTableau] = retourDelta;
					tailleTableau++;

					correspondanceEtat.insert(
							std::pair<etatset_t, etat_t>(retourDelta,
									correspondanceEtat.size()));
				}

				//Resize du tableau trans (cf. FromFile() )
				retour.trans.resize(tailleTableau + 1); 
				
				for (size_t h = 0; h < retour.trans.size(); h++) 
				{
					retour.trans[h].resize(at.nb_symbs);
				}

				/*std::cout << etatPourDelta << " => " << retourDelta
							<< "avec la lettre " << (symb_t) (ASCII_A + i)
							<< std::endl;*/

				//Insertion dans trans
				retour.trans[correspondanceEtat.at(etatPourDelta)][i].insert(correspondanceEtat.at(retourDelta)); 

			}

			//Si le prochain tour de boucle dépasse la taille de mon tableau
			if ((k + 1) > tailleTableau) 
			{
				//Continu = false et on sort du while()
				continu = false; 
			} else 
			{
				etatPourDelta.clear();
				
				//On prend chaque contenu de stockageDelta au fur et à mesure que la boucle tourne
				etatPourDelta = stockageDelta[k]; 
				k++;
			}
		}

		retour.nb_etats = correspondanceEtat.size();
		retour.nb_symbs = at.nb_symbs;

		retour.nb_finaux = 0;

		for (int i = 0; i < tailleTableau; i++) {
			if (ContientFinal(at, stockageDelta[i])) {
				retour.nb_finaux++;

				retour.finaux.insert(correspondanceEtat.at(stockageDelta[i]));
			}
		}

		retour.initial = 0;

		printf("Nouveaux etats :\n");

		bool initial = false;

		for (std::map<etatset_t, etat_t>::iterator it =
				correspondanceEtat.begin(); it != correspondanceEtat.end();
				++it) {
			printf("{");

			for (etatset_t::iterator it1 = it->first.begin();
					it1 != it->first.end(); it1++) {
				printf("%lu ", *it1);
				if (*it1 == 0) {
					initial = true;
				}
			}

			printf("} correspond à %lu", it->second);

			if (ContientFinal(retour, it->first)) {
				printf("(final)");
			}
			if (initial == true) {
				printf("(initial)");
			}

			printf("\n");

			initial = false;
		}

		printf("\n");

		printf("Nouvelle transitions :\n");

		for (std::map<etatset_t, etat_t>::iterator it =
				correspondanceEtat.begin(); it != correspondanceEtat.end();
				++it) {
			for (unsigned int j = 0; j < retour.nb_symbs; j++) {
				cout << "Delta(" << it->second << "," << (symb_t) (j + ASCII_A) << ") = {" << retour.trans[it->second][j] << "}" << std::endl;
			}
		}
	} else {
		return at;
	}

	return retour;

}

// -----------------------------------------------------------------------------
// Fonctions à compléter pour la seconde partie du projet
// -----------------------------------------------------------------------------

////////////////////////////////////////////////////////////////////////////////

bool ToGraph(sAutoNDE& at, string path) {

	std::ofstream file(path.c_str(), std::ofstream::out);

	if (file) 
	{
		file
		<< "digraph finite_state_machine {\nrankdir=LR;\nsize=\"10,10\"\n\nnode [shape = doublecircle];"; //En tête
		if(at.nb_finaux > 0)
		{
			file << at.finaux << ";";
		}
		//Etat finaux
		file << "\nnode [shape = point ]; q;\nnode [shape = circle];\n\n"; 
		
		//Etat initial
		file << "q -> " << at.initial << ";\n"; 

		for (unsigned int i = 0; i < at.trans.size(); i++) 
		{
			for (unsigned int j = 0; j < at.trans[i].size(); j++) 
			{
				for (etatset_t::const_iterator it = at.trans[i][j].begin(); it != at.trans[i][j].end(); it++) 
				{
					//On met dans le fichier toutes les transitions de l'automate.
					file << i << " -> " << *it << " [label = \""
							<< (symb_t) (j + ASCII_A) << "\"];" << endl; 
				}
			}
		}

		for (unsigned int i = 0; i < at.epsilon.size(); i++) // it1 = at.epsilon.begin() ; it1 != at.epsilon.end() ; it1++){
		{
			for (etatset_t::const_iterator it = at.epsilon[i].begin();
					it != at.epsilon[i].end(); it++) {
				file << i << " -> " << *it << "[label =\"e\"]" << endl;
			}
		}

		file << "\n}";

		return true;
	} 
	else 
	{
		std::cout << "Erreur d'ouverture du fichier";
		return false;
	}

	return false;
}

////////////////////////////////////////////////////////////////////////////////

// fonction outil : on garde x, et on "ajoute" trans et epsilon de y
// en renommant ses états, id est en décallant les indices des états de y
// de x.nb_etats
sAutoNDE Append(const sAutoNDE& x, const sAutoNDE& y) 
{
	assert(x.nb_symbs == y.nb_symbs);
	sAutoNDE r;
	
	//Le nombre d'état de r vaut celui de x plus celui de y
	r.nb_etats = x.nb_etats + y.nb_etats;
	
	//Le nombre de symboles de r vaut celui de x (ou y) car x.nb_symbs = y.nb_symbs
	r.nb_symbs = x.nb_symbs;
	
	//Le nombre d'état finaux de r vaut celui de x plus celui de y
	r.nb_finaux = x.nb_finaux + y.nb_finaux;
	
	//r prend l'état initial de x comme état initial
	r.initial = x.initial;

	//Resize des tableaux trans et epsilon de r.
	r.trans.resize(r.nb_etats);
	for (unsigned int i = 0; i < r.trans.size(); i++) 
	{
		r.trans[i].resize(r.nb_symbs);
	}
	
	r.epsilon.resize(x.epsilon.size() + y.epsilon.size());

	//On insère chaque états finaux de x dans r
	for (set<etat_t>::iterator it = x.finaux.begin(); it != x.finaux.end(); it++) 
	{
		r.finaux.insert(*it);
	}
	
	//Puis on insère ceux de y en changeant l'indice des états de + x.nb_etats  (pour crée des nouveaux états)
	for (set<etat_t>::iterator it = y.finaux.begin(); it != y.finaux.end(); it++) 
	{
		r.finaux.insert(x.nb_etats + *it);
	}
	
	//On fait de même pour trans de x et trans de y
	for (unsigned int i = 0; i < x.trans.size(); i++) 
	{
		r.trans[i] = x.trans[i];
	}
	//On insère les transitions de y avec les nouveau états
	for (unsigned int i = 0; i < y.trans.size(); i++) 
	{
		for (unsigned int j = 0; j < y.trans[i].size(); j++) 
		{
			for (etatset_t::const_iterator it = y.trans[i][j].begin(); it != y.trans[i][j].end(); it++) 
			{
				r.trans[i + x.nb_etats][j].insert(*it + x.nb_etats);
			}
		}
	}

	//Si x n'est pas déterministe, on insère les e-transitions de x dans r.
	if (!EstDeterministe(x)) 
	{
		for (unsigned int i = 0; i < x.epsilon.size(); i++) 
		{
			for (etatset_t::const_iterator it = x.epsilon[i].begin(); it != x.epsilon[i].end(); it++) 
			{
				r.epsilon[i].insert(*it);
			}
		}
	}
	
	//Si y n'est pas déterministe, on insère les e-transitions de x dans r.
	if (!EstDeterministe(y)) 
	{
		for (unsigned int i = 0; i < y.epsilon.size(); i++) 
		{
			for (etatset_t::const_iterator it = y.epsilon[i].begin(); it != y.epsilon[i].end(); it++) 
			{
				r.epsilon[i + x.nb_etats].insert(*it + x.nb_etats);
			}
		}
	}

	return r;
}

////////////////////////////////////////////////////////////////////////////////

sAutoNDE Union(const sAutoNDE& x, const sAutoNDE& y) 
{
	assert(x.nb_symbs == y.nb_symbs);
	
	sAutoNDE r = Append(x, y);

	//On créé un nouvel état
	etat_t nouvelEtatInitial = r.nb_etats;
	r.nb_etats++;

	//On resize les tableaux trans et epsilon de r en fonction du nouveau nombres d'états de r.
	r.epsilon.resize(r.nb_etats);

	r.trans.resize(r.nb_etats);
	r.trans[nouvelEtatInitial].resize(r.nb_symbs);

	r.epsilon[nouvelEtatInitial].insert(x.initial); //On ajoute une epsilon transition de ce nouvel etat vers l'état initial de x
	r.epsilon[nouvelEtatInitial].insert(y.initial + x.nb_etats); //On ajoute une epsilon transition de ce nouvel état vers l'état initial de y
	//Ce nouvel état devient l'état initial de r et l'union est donc crée
	r.initial = nouvelEtatInitial;
	return r;
}

////////////////////////////////////////////////////////////////////////////////

sAutoNDE Concat(const sAutoNDE& x, const sAutoNDE& y) 
{
	assert(x.nb_symbs == y.nb_symbs);
	sAutoNDE r = Append(x, y);

	for (etatset_t::const_iterator it = x.finaux.begin(); it != x.finaux.end();	it++) //Parcours des états finaux de x
	{
		//Epsilon transitions des etats finaux de x vers l'état initial de y
		r.epsilon[*it].insert(y.initial + x.nb_etats); 
		
		//On efface l'état final puisqu'il n'est plus final
		r.finaux.erase(*it);
		
		r.nb_finaux--;
	}

	return r;
}

////////////////////////////////////////////////////////////////////////////////

sAutoNDE Complement(const sAutoNDE& x) 
{
	sAutoNDE r = x;

	//Si r n'est pas déterministe, on le déterminise.
	if(!EstDeterministe(r))
	{
		r = Determinize(r);
	}

	etatset_t etat;

	//Pour chaque état de r
	for(unsigned int i = 0; i < r.nb_etats; i++)
	{
		//on insère l'état courant dans un etatset_t
		etat.insert(i);

		//Si l'etatset_t contient un etat final, on le supprime de l'ensemble des états finaux de r.
		if(ContientFinal(r, etat))
		{
			r.finaux.erase(i);
			r.nb_finaux--;
		}
		//Sinon, on transforme cet état en état final.
		else
		{
			r.finaux.insert(i);
			r.nb_finaux++;
		}

		//On vide l'etatset_t
		etat.clear();
	}

	return r;
}

////////////////////////////////////////////////////////////////////////////////

sAutoNDE Kleene(const sAutoNDE& x) 
{
	sAutoNDE r = x;

	//Pour chaque états finaux de r, on rajoute une e-transition entre cet état et l'état initial de r.
	for(etatset_t::const_iterator it = r.finaux.begin(); it != r.finaux.end(); it++)
	{
		r.epsilon[*it].insert(r.initial);
	}

	//L'état initial de x devient final.
	r.finaux.insert(r.initial);
	r.nb_finaux++;

	return r;
}

////////////////////////////////////////////////////////////////////////////////

sAutoNDE Intersection(const sAutoNDE& x, const sAutoNDE& y) 
{
	sAutoNDE atr1 = x, atr2 = y, unionDesDeux;

	//On fait le complément des automates x et y.
	atr1 = Complement(atr1);
	atr2 = Complement(atr2);
	
	//On fait l'union des compléments de x et y.
	unionDesDeux = Union(atr1, atr2);

	//Et on refait un complément sur l'union
	return Complement(unionDesDeux);
}

////////////////////////////////////////////////////////////////////////////////

//Fonction qui permet de compter les sysmboles d'une expression rationnelle.
void compteSymboleExpr(sExpressionRationnelle er, int& cpt)
{
	//On effectue un switch sur l'opérateur de l'expression rationnelle.
	switch(er->op)
	{
	case o_variable: 
		if(cpt < ((((er->nom)->c_str()[0]) - ASCII_A) + 1) && ((er->nom)->c_str()[0]) != 'e') //Si cpt < la valeur de la lettre et que la lettre != 'e'
		{
			cpt = ((er->nom)->c_str()[0] - ASCII_A) + 1; //On met à jour cpt
		}

		break;

	case o_ou:
		compteSymboleExpr(er->arg1, cpt); //Récursivité sur les deux arguments jusqu'à trouver une variable
		compteSymboleExpr(er->arg2, cpt);
		break;

	case o_concat:
		compteSymboleExpr(er->arg1, cpt); //Idem
		compteSymboleExpr(er->arg2, cpt);
		break;

	case o_etoile:
		compteSymboleExpr(er->arg, cpt); //Idem sur l'argument
		break;
	}
}

//Fonction qui permet de construire un automate à partir d'une expression rationnelle et du nombre de symbole de celle-ci
sAutoNDE constructionAutomate(sExpressionRationnelle er, int nb_symbs)
{
	sAutoNDE r;
	sAutoNDE tmp1, tmp2;

	//On effectue un switch sur l'opérateur de l'expression rationnelle.
	switch(er->op)
	{
	case o_variable:
		//On crée un nouvel pour chaque variable et on le retourne
		if((er->nom)->c_str()[0] != 'e') //Cas d'une variable qui n'est pas le mot vide
		{
			r.nb_etats = 2; //2 états
			r.initial = 0; //Un état initial
			r.nb_symbs = nb_symbs; //Nb_symbs = nb_symbs de l'automate que l'on va crée à la fin
			r.finaux.insert(1); //Un état final
			r.nb_finaux = 1;
			r.epsilon.resize(r.nb_etats);
			r.trans.resize(r.nb_etats);
			r.trans[0].resize(nb_symbs);
			r.trans[1].resize(nb_symbs);
			r.trans[0][((symb_t)(((er->nom)->c_str()[0])) - ASCII_A)].insert(1); //On crée une transition depuis l'état initial vers l'état final avec la lettre contenu dans 'nom' qui une o_variable
		}
		else //Cas de la lecture du mot vide
		{
			r.nb_etats = 1; //1 état
			r.initial = 0; //Cet état est initial
			r.nb_symbs = nb_symbs; //Nb_symbs = nb_symbs de l'automate que l'on va crée à la fin
			r.finaux.insert(0); //L'état initial est aussi final
			r.nb_finaux = 1;
			r.epsilon.resize(r.nb_etats);
			r.trans.resize(r.nb_etats);
			r.trans[0].resize(nb_symbs);
		}
		return r;
		break;

	case o_ou:
		tmp1 = constructionAutomate(er->arg1, nb_symbs); //Récursivité sur les deux arguments pour construire l'automate
		tmp2 = constructionAutomate(er->arg2, nb_symbs);

		r = Union(tmp1, tmp2); //On fait l'union des deux automates crées

		return r;
		break;

	case o_concat:
		tmp1 = constructionAutomate(er->arg1, nb_symbs); //Idem
		tmp2 = constructionAutomate(er->arg2, nb_symbs);

		r = Concat(tmp1, tmp2);

		return r;
		break;

	case o_etoile:
		r = constructionAutomate(er->arg, nb_symbs); //Idem sur l'argument
		r = Kleene(r);
		return r;
		break;
	}

	return r;
}

sAutoNDE ExpressionRationnelle2Automate(string expr) 
{
	sAutoNDE r;

	sAutoNDE at;

	int nb_symbs = 0;

	sExpressionRationnelle er = lit_expression_rationnelle(expr);

	compteSymboleExpr(er, nb_symbs); //Compte le nombre de symbole
	r = constructionAutomate(er, nb_symbs); //Construit l'automate

	cout << er << endl;

	return r;
}

////////////////////////////////////////////////////////////////////////////////

void Help(ostream& out, char *s) {
	out << "Utilisation du programme " << s << " :" << endl;
	out
	<< "-acc ou -accept Input Word:\n\t détermine si le mot Word est accepté"
	<< endl;
	out << "-det ou -determinize Input :\n\t déterminise Input" << endl;
	out << "-cup ou -union Input1 Input2 :\n\t calcule l'union" << endl;
	out << "-cat ou -concat Input1 Input2 :\n\t calcul la concaténation"
			<< endl;
	out << "-star ou -kleene Input :\n\t calcul de A*" << endl;
	out << "-bar ou -complement Input :\n\t calcul du complément" << endl;
	out << "-cap ou -intersection Input1 Input2 :\n\t calcul de l'intersection"
			<< endl;
	out
	<< "-expr2aut ou expressionrationnelle2automate ExpressionRationnelle :\n\t calcul de l'automate correspondant à l'expression rationnelle"
	<< endl;
	out << "-nop ou -no_operation Input :\n\t ne rien faire de particulier"
			<< endl;

	out
	<< "-o ou -output Output :\n\t écrire le résultat dans le fichier Output, afficher sur STDOUT si non spécifié"
	<< endl;
	out << "-g ou -graphe :\n\t l'output est au format dot/graphiz" << endl
			<< endl;

	out << "Exemple '" << s << " -determinize auto.txt -output determin.txt'"
			<< endl;
}

////////////////////////////////////////////////////////////////////////////////

int main(int argc, char* argv[]) {
	if (argc < 3) {
		Help(cout, argv[0]);
		return EXIT_FAILURE;
	}

	int pos;
	int act = -1;              // pos et act pour savoir quelle action effectuer
	int nb_files = 0;           // nombre de fichiers en entrée
	string str, in1, in2, out, acc, expr;
	// chaines pour (resp.) tampon; fichier d'entrée Input1; fichier d'entrée Input2;
	// fichier de sortie et chaine dont l'acceptation est à tester
	bool toFile = false, graphMode = false; // sortie STDOUT ou fichier ? Si fichier, format graphviz ?

	// options acceptées
	const size_t NBOPT = 11;
	string aLN[] = { "accept", "determinize", "union", "concat", "kleene",
			"complement", "intersection", "expressionrationnelle2automate",
			"no_operation", "output", "graph" };
	string aSN[] = { "acc", "det", "cup", "cat", "star", "bar", "cap",
			"expr2aut", "nop", "o", "g" };

	// on essaie de "parser" chaque option de la ligne de commande
	for (int i = 1; i < argc; ++i) {
		if (DEBUG)
			cerr << "argv[" << i << "] = '" << argv[i] << "'" << endl;
		str = argv[i];
		pos = -1;
		string* pL = find(aLN, aLN + NBOPT, str.substr(1));
		string* pS = find(aSN, aSN + NBOPT, str.substr(1));

		if (pL != aLN + NBOPT)
			pos = pL - aLN;
		if (pS != aSN + NBOPT)
			pos = pS - aSN;

		if (pos != -1) {
			// (pos != -1) <=> on a trouvé une option longue ou courte
			if (DEBUG)
				cerr << "Key found (" << pos << ") : " << str << endl;
			switch (pos) {
			case 0: //acc
				in1 = argv[++i];
				acc = argv[++i];
				nb_files = 1;
				break;
			case 1: //det
				in1 = argv[++i];
				nb_files = 1;
				break;
			case 2: //cup
				in1 = argv[++i];
				in2 = argv[++i];
				nb_files = 2;
				break;
			case 3: //cat
				in1 = argv[++i];
				in2 = argv[++i];
				nb_files = 2;
				break;
			case 4: //star
				in1 = argv[++i];
				nb_files = 1;
				break;
			case 5: //bar
				in1 = argv[++i];
				nb_files = 1;
				break;
			case 6: //cap
				in1 = argv[++i];
				in2 = argv[++i];
				nb_files = 2;
				break;
			case 7: //expr2aut
				expr = argv[++i];
				nb_files = 0;
				break;
			case 8: //nop
				in1 = argv[++i];
				nb_files = 1;
				break;
			case 9: //o
				toFile = true;
				out = argv[++i];
				break;
			case 10: //g
				graphMode = true;
				break;
			default:
				return EXIT_FAILURE;
			}
		} else {
			cerr << "Option inconnue " << str << endl;
			return EXIT_FAILURE;
		}

		if (pos < 9) {
			if (act > -1) {
				cerr << "Plusieurs actions spécififées" << endl;
				return EXIT_FAILURE;
			} else
				act = pos;
		}
	}

	if (act == -1) {
		cerr << "Pas d'action spécififée" << endl;
		return EXIT_FAILURE;
	}

	/* Les options sont OK, on va essayer de lire le(s) automate(s) at1 (et at2)
	 et effectuer l'action spécifiée. Atr stockera le résultat*/

	sAutoNDE at1, at2, atr;

	if ((nb_files == 1 or nb_files == 2) and !FromFile(at1, in1)) {
		cerr << "Erreur de lecture " << in1 << endl;
		return EXIT_FAILURE;
	}
	if (nb_files == 2 and !FromFile(at2, in2)) {
		cerr << "Erreur de lecture " << in2 << endl;
		return EXIT_FAILURE;
	}

	switch (act) {
	case 0: //acc
		cout << "'" << acc << "' est accepté: " << Accept(at1, acc) << endl;
		atr = at1;
		break;
	case 1: //det
		atr = Determinize(at1);
		break;
	case 2: //cup
		atr = Union(at1, at2);
		break;
	case 3: //cat
		atr = Concat(at1, at2);
		break;
	case 4: //star
		atr = Kleene(at1);
		break;
	case 5: //bar
		atr = Complement(at1);
		break;
	case 6: //cap
		atr = Intersection(at1, at2);
		break;
	case 7: //expr2aut
		atr = ExpressionRationnelle2Automate(expr);
		break;
	case 8: //nop
		atr = at1;
		break;
	default:
		return EXIT_FAILURE;
	}

	// on affiche le résultat ou on l'écrit dans un fichier
	if (!toFile)
		cout << atr;
	else {
		if (graphMode) {
			ToGraph(atr, out + ".gv");
			system(("dot -Tpng " + out + ".gv -o " + out + ".png").c_str());
		} else {
			ofstream f((out + ".txt").c_str(), ios::trunc);
			if (f.fail())
				return EXIT_FAILURE;
			f << atr;
		}
	}

	return EXIT_SUCCESS;
}

